package 二叉树.基础;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MyTree {
    private static TreeNode root;
    TreeNode creatTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode H = new TreeNode('H');

        A.left  = B;
        A.right = C;
        B.left = D;
        B.right = E;
//        C.right = H;
        root = A;
        return root;
    }

    //计算节点数
    int count = 0;
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }

    //方法2，左边的节点数加上右边的节点数，在加上根节点就是总共节点数
    public int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }

    //叶子节点数
    int leafNum =0;
    public int leaf(TreeNode root){
        if(root ==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            leafNum++;
        }
        leaf(root.left);
        leaf(root.right);
        return leafNum;
    }

    //方法2
    public int leaf2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return leaf2(root.left)+ leaf2(root.right);
    }

    //k层的节点数
    int getKLeveNodes(TreeNode root ,int k){
        if(root ==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLeveNodes(root.left,k-1)+getKLeveNodes(root.right,k-1);
    }

    //获得树的高度
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if(left>right){
            return left+1;
        }else {
            return right+1;
        }
    }

    //检查数是否存在
    public boolean find(TreeNode root,char key){
        if(root ==null){
            return false;
        }
        if(root.val==key){
            return true;
        }
        boolean boolean1 = find(root.left,key);
        if(boolean1 ==true){
            return true;
        }
        boolean boolean2 = find(root.right,key);
        if(boolean2==true){
            return true;
        }
        return false;
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        if(root == null){
            return ;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left !=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }

    //判断是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }

            while(!queue.isEmpty()){
                TreeNode cur1 = queue.poll();
                if(cur1!=null){
                    return false;
                }
            }
        return true;
    }





    public static void main(String[] args) {

        MyTree myTree = new MyTree();
        myTree.creatTree();

        int x1 = myTree.size(root);
        int x2 = myTree.size2(root);
        System.out.println("节点个数"+x1);
        System.out.println("节点个数"+x2);
        System.out.println("=======");
        int leafNum1 = myTree.leaf(root);
        System.out.println("叶子节点数"+leafNum1);
        System.out.println("======");
        int h = myTree.getHeight(root);
        System.out.println(h);
        //层序遍历
        myTree.levelOrder(root);
        System.out.println();
        //判断是不是完全二叉树
        System.out.println(myTree.isCompleteTree(root));
    }
    
}
